/*
 * kmpsearchalgorithm.h
 *
 *  Created on: Nov 14, 2010
 *      Author: Satish
 */

#include"genericsearchalgorithm.h"

#ifndef KMPSEARCHALGORITHM_H_
#define KMPSEARCHALGORITHM_H_

//KmpSearchAlgorithm is a derived class of GenericSearchAlgorithm
//It provides an implementation for the Abstract method substringSearch
class KmpSearchAlgorithm:public GenericSearchAlgorithm
{

private:
	int *mPartialMatchTable;//table that gives the amount of backtracking
	                         // required when a mismatch occurs at a particular index
public:
	KmpSearchAlgorithm();
	virtual char* substringSearch(const char *haystack ,const char *needle) ;
	//function used to compute the entries for the partialMatchTable
	void populatePartialMatchTable(const char *needle);
	virtual ~KmpSearchAlgorithm();

};

#endif /* KMPSEARCHALGORITHM_H_ */
